# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    def IsBalanced_Solution(self, p):
        # write code here
    #     if not p:
    #         return True
    #     return self.help(p) and self.IsBalanced_Solution(p.left) and self.IsBalanced_Solution(p.right)
    #
    # def help(self, node):
    #     if not node:
    #         return 0
    #
    #     l = self.help(node.left)
    #     r = self.help(node.right)
    #     if abs(l - r) > 1:
    #         return False
    #     return max(l,r)+1
        return self.help(p) != -1
    def help(self,p):
        if p == None:
            return 0

        l = self.help(p.left)

        r = self.help(p.right)

        if l or r ==-1:
            return  -1
        if abs(l - r) > 1:
            return -1
        else:
            return max(l, r) + 1

m1 = TreeNode(1)
m1.left = TreeNode(2)
m1.right = TreeNode(3)
m1.left.left = TreeNode(4)
# m1.left.left.left = TreeNode(3)
# m1.left.left.right = TreeNode(3)
# m1.left.left.left.left = TreeNode(4)
# m1.left.left.left.right = TreeNode(4)
m1.right.right = TreeNode(2)
m1.right.right.right = TreeNode(2)
m1.right.right.right.right = TreeNode(2)
m1.right.right.right.right.right = TreeNode(2)
s = Solution()

t = s.IsBalanced_Solution(m1)
print(t)
